import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * Created with IntelliJ IDEA.
 * Description: 优先级队列的模拟实现与练习
 */

class Heap{
    public int[] elem = new int[DEFAULT_SIZE];
    private int usedSize;
    private static final int DEFAULT_SIZE = 10;

    public Heap() {
        this.elem = new int[DEFAULT_SIZE];
    }

    public Heap(int[] elem) {
        for (int i = 0; i < elem.length; i++) {
            this.elem[i] = elem[i];
        }
    }

    public void createHeap(int[] array) {

        for (int i = 0; i < array.length; i++) {
            if(usedSize == this.elem.length) {
                elem = Arrays.copyOf(elem,elem.length + elem.length>>>1);
            }
            this.elem[i] = array[i];
            usedSize++;
        }
        for (int i = (usedSize - 1 - 1) / 2; i >= 0; i--) {
            shiftDown(this.elem,i);
        }
    }

    public void shiftDown(int[] array,int parent) {
        while(parent * 2 + 1 < usedSize) {
            int child = parent * 2 + 1;
            if (child + 1 < usedSize && array[child] < array[child + 1]) {
                child += 1;
            }
            if (array[parent] < array[child]) {
                int tmp = array[child];
                array[child] = array[parent];
                array[parent] = tmp;
            }else {
                break;
            }
            parent = child;
        }
    }
}

public class Test {
    /**
     * 著名的TopK问题：得到前 k 个小的值，顺序无所谓
     * @param arr 传入的数组
     * @param k 具体前 K 个小的元素
     * @return 前 k 个小的值的数组
     */
    public int[] smallestK(int[] arr, int k) {
        //当arr == null 或者 K是0的时候，需要直接返回
        if(arr == null || k == 0) {
            return new int[0];
        }
        //创建一个大根堆
        PriorityQueue<Integer> pq = new PriorityQueue<>(k,new Comparator<Integer>(){
            @Override
            public int compare(Integer o1, Integer o2) {
                return o2.compareTo(o1);
            }
        });
        for(int i = 0; i < k; i++) {
            pq.offer(arr[i]);
        }
        for(int i = k; i < arr.length; i++) {
            int tmp = pq.peek();
            if(arr[i] < tmp) {
                pq.poll();
                pq.offer(arr[i]);
            }
        }
        int[] nums = new int[k];
        for(int i = 0; i < k; i++) {
            nums[i] = pq.poll();
        }
        return nums;
    }
    public static void main1(String[] args) {
        int[] arr = { 27,15,19,18,28,34,65,49,25,37 };
        Heap heap = new Heap();
        heap.createHeap(arr);
        System.out.println("hjgl");
    }
}
